package exercise.基础练习;

import util.ArrayUtil;

public class 差分数组 {
    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(10, 0, 30);
        DifferenceArray diff_arr = new 差分数组().new DifferenceArray(arr);
        ArrayUtil.print(arr);
        ArrayUtil.print(diff_arr.diff);
    }

    class DifferenceArray {
        private int[] diff;//差分数组

        /**
         * 构造方法：根据参数的数组创建一个差分数组
         */
        public DifferenceArray(int[] nums) {
            diff = new int[nums.length];
            diff[0] = nums[0];
            for (int i = 1; i < diff.length; i++) {
                diff[i] = nums[i] - nums[i - 1];
            }
        }

        /**
         * 将数组索引i到j的元素值增加value
         */
        public void increment(int i, int j, int value) {
            diff[i] += value;
            if (j + 1 < diff.length) {
                diff[j + 1] -= value;
            }
        }

        /**
         * 根据差分数组计算目标数组
         */
        public int[] target() {
            int[] result = new int[diff.length];
            result[0] = diff[0];
            for (int i = 1; i < result.length; i++) {
                result[i] = result[i - 1] + diff[i];
            }
            return result;
        }
    }
}


